1. Field of the Invention
The present invention relates to a method and apparatus for bypassing a spanning tree constructed in a network.
The explosive growth of the Internet in recent years has brought about a need for a wide-area LAN with which a network can be constructed, in an inexpensive way, as a network within a corporation or a provider providing Internet services to home users.
To achieve this, a spanning tree more efficient than a traditional spanning tree must be constructed in a wide-area LAN in order to make efficient use of network resources.
2. Description of the Related Art
In a LAN constructed with a plurality of nodes, a network of a tree structure containing no loops can be constructed using Spanning Tree Protocol (hereinafter abbreviated STP). STP is an important protocol defined in IEEE 802.ID-1998 as a required function.
A network constructed based on STP has a loop-free tree structure with a root node at its apex by setting blocking ports that cannot perform data transfer.
For example, in FIG. 1, by exchanging BPDU (Bridge Protocol Data Unit) messages between bridges, bridge 1 is determined as the root node in accordance with a prescribed rule. At this time, of the ports on each of the segments defined by line segments in the figure connecting between the bridges 1 to 6, the port closest to the root node is determined as a designated port which is indicated by a solid black square in the figure. Further, of the ports on each bridge, the port closest to the root node is determined as a root port which is indicated by a solid black circle in the figure. Any other port that is neither a designated port nor a root port is a blocking port which is indicated by a mark in the figure. In this way, a spanning tree, shown by thick lines in the figure, is formed.
While setting such blocking ports has the advantage of preventing the occurrence of loops, the following problems arise because of the existence of unused routes: (i) since traffic is concentrated at the root node, congestion occurs near the root node, (ii) if there is a better route than the route passing through the root node, such a route is not used, resulting in inefficient use of network resources, and (iii) delays occur as a result of (i) and (ii).
To solve these problems, Japanese Unexamined Patent Publication No. 11-355337 proposes that a route not used in a tree structure be made usable so that data can be transferred by bypassing the root node.
As shown in FIG. 2, according to the technique proposed in the above publication, a node (for example, bridge 4) that has a blocking port transmits a bypass route setup request (bypass request) 10 to a destination node (bridge 3) in a network constructed using a spanning tree. The node that received the bypass request rewrites the routing table in accordance with the routing information contained in the bypass request. Then, a bypass response 12 is returned to the requesting node by including therein routing information concerning a designated port. The node that received the bypass response rewrites the routing table in accordance with the routing information contained in the response, and transmits data to the destination node by using the thus constructed bypass route.
The above bypass route construction method is not realistic for the following reason.
In a network constructed using a spanning tree, address learning is an indispensable and important function, and a forwarding table for identifying the destination is constructed using this function. In the above method, however, no mention whatsoever is made of address learning, but it is only stated that a bypass route is constructed based on STP information; if a bypass route is constructed by the above method, when it comes to actually transmitting data, it is not known on which bypass route the data should be transmitted because address learning is not considered and, in reality, it is not possible to use the bypass route. It is also not known at which timing the bypass request is to be sent out. If it is assumed that the bypass request is sent out at the time that the blocking port is recognized, the information to be exchanged between the bridges has not yet been created at that time; on the other hand, if it is assumed that the request is sent out at the time that address learning is done, this would means sending out a bypass request each time each node in the network performs address learning, and sending out bypass requests so frequently is not realistic when the network load and the processing capability of each node are considered.
Accordingly, with the above prior art, it is not realistically possible to use a bypass route.
Furthermore, the above-described method assumes that a routing table holds destination network (LAN), metrics, and next node information is managed at that node; however, while holding such information is possible at Layer 3, at Layer 2 it is not possible to know to which network (LAN) the destination address belongs, and besides, exchange of routing information between nodes is not performed (not defined in the IEEE 802.ID), so that in reality such a routing table cannot be used at Layer 2.